package problems; 
import static lib.MathLib.factorize;
import static lib.MathLib.multiplicativeOrder;

import java.math.BigDecimal;
import java.math.BigInteger;
import java.util.Arrays;
import java.util.List;

import lib.MathLib;

/**
 * TODO: prove that only prime denominators are candidates for the longest repetend
 * @author laszlo
 *
 */
public class Euler026 extends AbstractEuler {

	private static final int SCALE = 500;
	private static final List<Long> PRIME_FACTORS_OF_TEN = Arrays.asList(2L,5L);
	
	@Override
	public Number calculate() {
		
		int maxRecurringFor = 3;
		int maxRecurring = 1;
		
		for (int i = maxRecurringFor; i <= 1000; i++) {

			BigDecimal division =
				BigDecimal.ONE.setScale(SCALE)
				.divide(BigDecimal.valueOf(i).setScale(SCALE), BigDecimal.ROUND_HALF_UP)
				.stripTrailingZeros();
			division.scale();//to prevent warning
//			System.out.println(i + ":\t" + division);
			
			if (i % 2 == 0 || i % 5 == 0) {
				List<Integer> factors = factorize(i);
				int twos = 0, fives = 0;
				while (factors.remove(2L)) twos++;
				while (factors.remove(5L)) fives++;
				factors.removeAll(PRIME_FACTORS_OF_TEN);
				if (factors.isEmpty()) {
					//System.out.println("only coprimes to 10, should not be recurring (finite length: " + BigDecimal.ONE.divide(new BigDecimal(i.longValue())).scale() + ")"); //this doubles as a check because an exception will be thrown if the division does turn out to be recurring
				} else {
					//System.out.println("the transient is of size " + max(twos, fives) + ", whereas the repetend can never be greater than that of 1/" + getProduct(factors));
				}
			} else if (MathLib.isPrime(i)) {
				int order = multiplicativeOrder(BigInteger.valueOf(10), BigInteger.valueOf(i)).intValue();
				//System.out.println("prime, so repeats right from the start with length " + order);
				if (order > maxRecurring) {
					maxRecurring = order;
					maxRecurringFor = i;
				}

			} else {
				//see http://en.wikipedia.org/wiki/Recurring_decimal#Reciprocals_of_composite_integers_coprime_to_10
				//System.err.println(i + " is not prime but is coprime because it contains only these factors: " + factorize(i.longValue()) + "; we need the Carmichael function to calculate the exact length of the repetend. But this is irrelevant because the length can never be greater than that of 1/[one of the factors] (right?)");
			}
		}
		
		return maxRecurringFor;
	}

	@Override
	protected Number getCorrectAnswer() {
		return 983;
	}

}
